package com.lft.sort04.shell_sort;

import java.util.Arrays;

/**
 * 【希尔排序】
 */
public class ShellSort {
	public static void main(String[] args) {
		int[] a = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
		System.out.println(Arrays.toString(shellSort(a)));
	}
	
	public static int[] shellSort(int[] a) {
		// 希尔排序的时间复杂度：平均：O(nlogN)，最差：O(n^s(1<s<2))
		int j;
		int temp;
		// 【移位式】
		for (int gap = a.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < a.length; i++) {
				j = i;
				temp = a[j];
				if (a[j] < a[j - gap]) {
					while (j - gap >= 0 && temp < a[j - gap]) {
						// 移动
						a[j] = a[j - gap];
						j -= gap;
					}
					// 退出while 循环时就给temp找到插入的位置
					a[j] = temp;
				}
			}
			// System.out.println("希尔排序第 " + ++count + " 轮 " + Arrays.toString(a));
		}
		return a;
		
		// // 【交换式】
		// int temp;
		// int count = 0;
		// for (int gap = a.length / 2; gap > 0; gap /= 2) {
		// 	for (int i = gap; i < a.length; i++) {
		// 		for (int j = i - gap; j >= 0; j -= gap) {
		// 			if (a[j] > a[j + gap]) {
		// 				temp = a[j];
		// 				a[j] = a[j + gap];
		// 				a[j + gap] = temp;
		// 			}
		// 		}
		// 	}
		// 	// System.out.println("希尔排序第 " + ++count + " 轮 " + Arrays.toString(a));
		// }
		// return a;
		
		//
		// int temp;
		// // 使用逐步推导方式
		// // 第 1 轮：将 10 个数据分成了 5 组
		// for (int i = 5; i < a.length; i++) {
		// 	// 遍历各组中所有的元素（共 5 组，每组有 2 个元素）步长 5
		// 	for (int j = i - 5; j >= 0; j -= 5) {
		// 		// 当前元素大于加上步长后的那个元素，说明要交换。
		// 		if (a[j] > a[j + 5]) {
		// 			temp = a[j];
		// 			a[j] = a[j + 5];
		// 			a[j + 5] = temp;
		// 		}
		// 	}
		// }
		//
		// // 第 2 轮：将 10 个数据分成了 2 组
		// for (int i = 5 / 2; i < a.length; i++) {
		// 	// 遍历各组中所有的元素（共 5 组，每组有 2 个元素）步长 5
		// 	for (int j = i - 5 / 2; j >= 0; j -= 5 / 2) {
		// 		// 当前元素大于加上步长后的那个元素，说明要交换。
		// 		if (a[j] > a[j + 5 / 2]) {
		// 			temp = a[j];
		// 			a[j] = a[j + 5 / 2];
		// 			a[j + 5 / 2] = temp;
		// 		}
		// 	}
		// }
		//
		// // 第 3 轮：将 10 个数据分成了 1 组
		// for (int i = 5 / 2 / 2; i < a.length; i++) {
		// 	// 遍历各组中所有的元素（共 5 组，每组有 2 个元素）步长 5
		// 	for (int j = i - 5 / 2 / 2; j >= 0; j -= 5 / 2 / 2) {
		// 		// 当前元素大于加上步长后的那个元素，说明要交换。
		// 		if (a[j] > a[j + 5 / 2 / 2]) {
		// 			temp = a[j];
		// 			a[j] = a[j + 5 / 2 / 2];
		// 			a[j + 5 / 2 / 2] = temp;
		// 		}
		// 	}
		// }
		// return a;
	}
}
